package com.hdu.other.tanxin;

import java.util.PriorityQueue;

public class lc871 {
    class Solution {
        public int minRefuelStops(int target, int startFuel, int[][] stations) {
             if (startFuel >= target) {
                 return 0;
             }
             int cur = startFuel;
             PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
             int ans = 0;
             for (int i = 0; i < stations.length; i++) {
                 int[] curStation = stations[i];
                 int to = curStation[0];
                 int fuel = curStation[1];
                 if (cur < to) {
                     while (cur < to && !pq.isEmpty()) {
                         cur += pq.poll();
                         ans++;
                     }
                     if (cur < to) {
                         return -1;
                     }
                     if (cur >= target) {
                         return ans;
                     }
                 }
                 pq.offer(fuel);
             }

             while (cur < target && !pq.isEmpty()) {
                 cur += pq.poll();
                 ans++;
                 if (cur >= target) {
                     return ans;
                 }
             }

             return -1;
        }
    }
}
